class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        // 状态表示 - 以第 i 个位置为节为的子数组的最大/小乘积
        int[] f = new int[n]; // 最大
        int[] g = new int[n]; // 最小
        // 初始化
        f[0] = nums[0];
        g[0] = nums[0];
        // 状态转移方程
        int ret = f[0];
        for(int i = 1; i < n; i++){
            if(nums[i] > 0){
                f[i] = Math.max(nums[i], f[i - 1] * nums[i]);
                g[i] = Math.min(nums[i], g[i - 1] * nums[i]);
            } else {
                f[i] = Math.max(nums[i], g[i - 1] * nums[i]);
                g[i] = Math.min(nums[i], f[i - 1] * nums[i]);
            }
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }
}